package LimitedTimeGame.Day_0217;

/**
 * @author zxc
 * @date 2023/02/17 11:24
 **/

/**
 * 题目 ：最大的以1为边界的正方形
 * 题目详述 ：
 * 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形子网格，
 * 并返回该子网格中的元素数量。如果不存在，则返回 0。
 *
 * 提示：
 * 1 <= grid.length <= 100
 * 1 <= grid[0].length <= 100
 * grid[i][j] 为 0 或 1
 *
 */
public class Largest1BorderedSquare {
    public static void main(String[] args) {
        System.out.println(largest1BorderedSquare(new int[][]{{0,0,0,1}}));
    }
    /**
     * 思路 ：
     * 即，通过从大到小对于所能够取得的最大正方形子网格，进行遍历;
     * （1）若是满足条件的话，则选择直接return;
     * （2）若是不满足条件的话，则选择继续循环遍历;
     * @param grid
     * @return
     */
    public static int largest1BorderedSquare(int[][] grid) {
        // 记录数组grid的行数/记录数;
        int row = grid.length;
        // 记录数组grid的列数;
        int col = grid[0].length;
        // 由于最大的正方形网格只能够去min(row ,col)
        int len = Math.min(row , col);
        // 从大到小遍历正方形网格的长度;
        for(int i = len; i > 0 ; i--){
            // 遍历当前边长为i正方形网格的所有情况;
            for(int j = 0 ; j <= col - i ; j++){
                for(int k = 0 ; k <= row  - i ; k++){
                    // 判断当前正方形网格是否边缘皆为"1";
                    if(isBorderedSquare(grid , k , j , i)){
                        return i * i;
                    }
                }
            }
        }
        return 0;
    }
    // 判断当前正方形网格的边缘是否皆为"1";
    private static boolean isBorderedSquare(int[][] grid, int a, int b, int len) {
        for(int i = a ; i < a + len ; i++){
            if(grid[i][b] == 0 || grid[i][b + len - 1] == 0){
                return false;
            }
        }
        for(int i = b + 1 ; i < b + len - 1 ; i++){
            if(grid[a][i] == 0 || grid[a + len - 1][i] == 0){
                return false;
            }
        }
        return true;
    }
}
